package com.demo.jzoffer2;

import com.demo.domain.ListNode;
import org.junit.Test;

/**
 * @author gy
 * @date 2022/12/1
 */
public class Test1201_01 {
    /**
     * 输入一个链表，输出该链表中倒数第k个节点。为了符合大多数人的习惯，本题从1开始计数，即链表的尾节点是倒数第1个节点。
     * <p>
     * 例如，一个链表有 6 个节点，从头节点开始，它们的值依次是 1、2、3、4、5、6。这个链表的倒数第 3 个节点是值为 4 的节点。
     *
     * @param head
     * @param k
     * @return
     */
    public ListNode getKthFromEnd(ListNode head, int k) {
        // 思路分析
        /**
         * 倒数第k个节点，正数第 n-k个节点
         * 需要获得链表的长度 n，然后顺序遍历
         */
        int n = 0;
        ListNode node;
        // 注意：node不为null
        for (node = head; node != null; node = node.next) {
            n++;
        }
        for (node = head; n - k > 0; n--) {
            node = node.next;
        }
        return node;
    }

    @Test
    public void m1() {
    }

}

